A primary advantage of a storage system with a storage array (i.e., a plurality of storage units) is its ability to recover data even when one (or more) of the storage units of the storage array has failed (and its associated data has been lost). Data recovery, in general, is enabled by storing data in a redundant manner. In the simplest form of data redundancy, data is mirrored (e.g., data is stored twice, so that if one copy of the data is lost, the other copy of the data remains and can be used to recover the lost data). Another form of data redundancy involves computing parity, in which a string of binary data is XOR'ed to form a parity bit. If one of the data bits of the binary string is lost, the parity bit can be used to recover the lost data bit.
There are certain tradeoffs between data mirroring and parity. Data mirroring is typically less efficient in terms of the use of storage space than a redundancy scheme employing parity. On the other hand, data mirroring typically provides more data redundancy (and hence a higher degree of data protection) than parity. One approach that attempts to strike a balance between the two approaches is multi-parity. For example, in a dual-parity scheme, two parity bits may be used to provide redundancy for a string of bits, allowing up to two bits of the data string to be recovered. A multi-parity approach is more efficient in terms of the use of storage space than data mirroring, while at the same time is more robust to data loss than a single parity approach. Multi-parity data redundancy schemes will be further discussed below.
A challenge that arises in data redundancy schemes for storage arrays is how to properly distribute data blocks and error-correction blocks (e.g., parity blocks) among the storage units of a storage array. If a data block and its associated error-correction block are both stored on the same storage unit, that data block is lost if the storage unit fails. Accordingly, it is essential that a data block and its associated error-correction block be stored on separate storage units to preclude the above-described scenario in which the failure of a single storage unit could result in the permanent loss of data.
A simple scheme that satisfies such constraint is the use of a dedicated parity storage unit (or more generally, a dedicated error-correction storage unit). For instance, four storage units can be used to store data, while a fifth storage unit is dedicated for parity. RAID 3 (RAID being an acronym for a redundant array of independent disks) is an example of a data redundancy scheme that employs a dedicated parity storage unit.
One common approach to manage how data is distributed onto a collection of storage units is data striping (or striping for brevity). In data striping, data is divided into a plurality of data blocks, and typically contiguous data blocks are grouped into a data stripe (or stripe for brevity). Data blocks of each stripe are distributed among the storage array. For instance in a stripe with four data blocks, the first data block could be stored on a first storage unit, the second data block could be stored on a second storage unit, and so on. Each stripe typically has one or more error-correction blocks to provide data redundancy. In the example above of storing a stripe with four data blocks, four storage units could be employed to store the four data blocks, while a fifth storage unit could be employed to store an error-correction block associated with the four data blocks.
While a dedicated parity storage unit is a simple approach to physically segregate any data block from its associated error-correction block, such approach has drawbacks. During any write to the storage array, the error-correction block associated with the modified data block will also need to be updated. As a result, the dedicated parity storage unit must be accessed during every data write, creating a heavy load (and possibly reduced response time) for the dedicated parity storage unit. One improvement to a dedicated parity storage unit is the use of rotated parity, in which parity blocks are distributed (or “rotated”) among the storage units of the storage array. To be more precise, in a rotated parity scheme, the parity block(s) of one stripe are stored on a first storage unit, while the parity block(s) of another stripe are stored on a second storage unit. In such a scheme, write activity due to parity updates is distributed more evenly among the storage units of the storage array, eliminating the bottleneck associated with a dedicated parity storage unit.
RAID 6 is an example of a data redundancy scheme that employs rotated parity. For clarity of description, one RAID 6 implementation (specifically the “left symmetric” variant) is depicted in FIG. 1. Eight disks (or more generally, eight storage units) are depicted in FIG. 1. Disk 0 through disk 6 store data blocks and error correcting blocks, while disk 7 is designated as a spare. In its role as a spare, disk 7 is typically not activated unless one of disk 0 through disk 6 has failed.
For clarity of description, reference labels are used to refer to particular data blocks. For instance, d.00 is a reference label used to refer to a data block stored on disk 0. For clarity of notation, reference labels associated with data blocks begin with the letter “d”, while reference labels associated with error-correction blocks begin with any one of the letters “P”, “Q” or “R”. For clarity of presentation, error-correction blocks are illustrated with a striped pattern. The information stored by a data block is typically in the form of a binary string (e.g., “0010101001 . . . ”). Similarly, information stored by an error-correction block is typically in the form of a binary string (e.g., “10101010100 . . . ”). It is noted that the spare disk (i.e., disk 7) does not actually store “SP”. “SP” is merely used as a label to designate disk 7 as a spare disk in FIG. 1.
The data blocks and error-correction blocks from each row of FIG. 1 belong to a single stripe. As can be seen from FIG. 1, each stripe contains two error-correction blocks, and hence, RAID 6, in addition to employing rotated parity, also employs multi-parity, specifically dual-parity. While error-correction blocks are distributed (or rotated) among the disks, the above-noted property of storing a data block separately from its associated error-correction block(s) is still preserved (i.e., a disk never stores a data block and an error-correction block from the same stripe).
In RAID 6, a spare disk (i.e., disk 7 in the example of FIG. 1) is idle during normal operation of the storage array (i.e., when all disks are operational), and is activated only upon failure of any one of the disks. Content of the failed disk may be reconstructed onto the spare disk, and upon the completion of the data reconstruction, the spare disk may substitute in place of the failed disk. While a disk is failed (i.e., is non-operational) and before the content of the failed disk is fully reconstructed onto the spare, the storage array operates in a degraded mode of operation. In the degraded mode, the storage array can still process read and write requests, but its response time to such requests is typically slower than in a normal operation in which all disks are operational. A benefit of having a spare is the reduction in the amount of time that the storage array is operated in a degraded mode of operation (i.e., a spare can be immediately activated and reconstruction can start, as compared to the alternative without a spare, in which a spare needs to be shipped from a warehouse, connected to the storage array and then activated, before reconstruction can start). A spare, however, comes with the tradeoff of adding cost to a storage system.
FIG. 2 depicts a RAID 7 implementation (specifically, a left symmetric variant). The RAID 7 implementation is presented as a comparison to the RAID 6 implementation of FIG. 1. For a fair comparison, the number of disks between the two implementations is the same (i.e., 8 disks), and the data capacity is also unchanged (i.e., the two RAID schemes are capable of storing the same number of data blocks). An advantage of the RAID 7 implementation over the RAID 6 implementation is its added redundancy (i.e., triple-redundancy instead of dual-redundancy). On the other hand, the RAID 7 implementation has the drawback of not having a spare disk, as compared to the RAID 6 implementation with the same number of storage units. As explained above, in the event of a disk failure, the RAID 7 implementation would be forced to operate in a degraded mode of operation for an extended period of time until a replacement disk arrives (e.g., a day could be quite typical of such a time period).